package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/8 9:59
 */

import java.util.Arrays;

/**
 * 困难题
 *
 * 给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。
 *
 * 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,1,2,6,7,5,1], k = 2
 * 输出：[0,3,5]
 * 解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
 * 也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
 *
 * 示例 2：
 *
 * 输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
 * 输出：[0,2,4]
 */
public class Demo_73_No689 {

    public static void main(String[] args) {
        int[] nums = new int[]{4, 5, 10, 6, 11, 17, 4, 11, 1, 3};
        System.out.println(Arrays.toString(maxSumOfThreeSubarrays(nums, 1)));

    }

    /**
     * 滑动窗口
     * @param nums
     * @param k
     * @return
     *
     * [4, 5, 10, 6, 11, 17, 4, 11, 1, 3]
     * 1
     */
    public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1=0,sum2=0,sum3=0; //三个窗口分别的总和
        int max1=0,max2=0,max3=0;
        int maxIndex1=0,maxIndex2_1=0,maxIndex2_2=0;

        for (int i = 2*k; i < nums.length; i++) {
            sum1 += nums[i-2*k];
            sum2 += nums[i-k];
            sum3 += nums[i];
            if(i >= 3*k-1){
                //第一次进来，其实就是 1 2 3 第一次满，这个时候会初始化第一次的三个值
                if(sum1>max1){
                    max1 = sum1;
                    maxIndex1 = i-3*k+1;
                }
                if(max1+sum2>max2){
                    max2 = max1+sum2;
                    maxIndex2_1 = maxIndex1;
                    maxIndex2_2 = i-2*k+1;
                }
                if(max2+sum3>max3){
                    max3 = max2+sum3;
                    ans[0] = maxIndex2_1;
                    ans[1] = maxIndex2_2;
                    ans[2] = i-k+1;
                }
                //减去的是当前位置的前缀数
                sum1 -= nums[i-3*k+1];
                sum2 -= nums[i-2*k+1];
                sum3 -= nums[i-k+1];
            }
        }
        return ans;
    }

    static int[] answer(int[] nums,int k){
        int[] ans = new int[3];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.length; ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }


    /**
     * dp法
     * 看不懂 但是再看要有郁闷症了 改日再看把
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSumOfThreeSubarrays_dp(int[] nums, int k) {
        int len = nums.length;
        //dp关键 找好i,j值
        int[][] dp = new int[len][3];

        int[] pre = new int[len+1];

        //以后可以经常用这个
        //pre[i] - pre[k] ==> i位置到k位置的和
        for(int i = 0; i < len; i++){
            pre[i+1] = pre[i]+nums[i];
        }

        for (int i = k; i < len; i++) {
            int s1 = i-k;
            int diff = pre[i]-nums[s1];
            dp[i-1][0]=i-1==0?diff:Math.max(dp[i-2][0],diff);

            int s2 = i-2*k;
            if(s2>=0){
                dp[i-1][1]=Math.max(dp[i-2][1],dp[i-k-1][0]+diff);
            }
            int s3 = i-3*k;
            if(s3>=0){
                dp[i-1][2]=Math.max(dp[i-2][2],dp[i-k-1][1]+diff);
            }
        }

        int[] ans = new int[3];
        int p = len-1;
        for(int i = 2; i>=0; i--){
            int max = dp[p][i];
            while (p-1>=0 && dp[p-1][i]==max)
                --p;
            ans[i]=p+1-k;
            p = p-k;
        }

        return ans;

    }


}
